package com.leetcode;

/**
 * 318. 最大单词长度乘积 (中等)
 * <p>
 * 给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
 */
public class LeetCode318 {

    public static void main(String[] arg0) {
        String[] words = new String[]{"a","ab","abc","d","cd","bcd","abcd"};
        System.out.println("最大单词长度乘积 = " + maxProduct(words));
    }

    public static int maxProduct(String[] words) {
        int maxRes = 0;
        int length = words.length;
        int[] masks = new int[length];

        // 计算每个字符串的位掩码
        for (int i = 0; i < length; i++) {
            String curr = words[i];
            for (int j = 0; j < curr.length(); j++) {
                masks[i] |= 1 << (curr.charAt(j) - 'a');
            }
        }

        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                // 用 & 与计算判断两个字符串有没有相同字母
                if ((masks[i] & masks[j]) == 0) {
                    int res = words[i].length() * words[j].length();
                    maxRes = Math.max(maxRes, res);
                }
            }
        }
        return maxRes;
    }

}
